home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / compute.arc / COMPUTE.PAS < prev   
Encoding:
Pascal/Delphi Source File  |  1980-01-01  |  9.9 KB  |  287 lines
  1. (*COMPUTE - by James da Silva    November 12, 1985
  2.  
  3.  
  4.   This simple program was written to illustrate the mechanics of expression
  5.   evaluation using recursive-descent techniques.  It's a poor man's resident
  6.   calculator program.  Well, ok, it isn't resident and it isn't exactly a
  7.   calculator, but it was fun, and believe it or not, I've actually found
  8.   myself using it once or twice.
  9.  
  10.   Compute calculates the value of the arithmetic expression passed to it on
  11.   the command line, then prints this value on the screen.
  12.  
  13.  
  14.   Here is the BNF syntax for compute:
  15.  
  16.      expression ::= term { add_operator term }.
  17.  
  18.      term ::= factor { mul_operator factor }.
  19.  
  20.      factor ::= terminal | '-' terminal.
  21.  
  22.      terminal ::= number_constant | '(' expression ')'.
  23.  
  24.  
  25.      add_operator ::= '+' | '-'.
  26.  
  27.      mul_operator ::= '*' | '/'.
  28.  
  29.      number_constant ::= digit {digit} { '.' {digit} }.
  30.  
  31.  
  32.      COMPUTE could be easily extended to handle:
  33.  
  34.         1. general output of numbers (i.e. 3 instead of 3.000,
  35.            3.1415926 instead of 3.1416)
  36.         2. hex and binary numbers.
  37.         3. multi-line expressions.
  38.         4. multiple expressions, carry-over of result. (a calculator)
  39.         5. builtin functions.
  40.  
  41.     Anyone care to try one?
  42.  
  43. *)
  44.  
  45. PROGRAM compute;
  46.  
  47.     TYPE
  48.  
  49.         token_type = (number, unknown, lparen,   { these are all the things }
  50.                       rparen, plus, minus,       { that can appear in our   }
  51.                       times, divide, endt);      { expressions. Note the    }
  52.                                                  { endt (end of text) and   }
  53.                                                  { unknown tokens.          }
  54.  
  55.         String128 = string [128];
  56.  
  57.     VAR
  58.         token: token_type;
  59.         number_value, expr_value: real;
  60.  
  61.         position, start_of_token: integer;
  62.         line: string128 absolute cseg: $80;  { the command line, in person }
  63.  
  64.  
  65.     {    USAGE - called when nothing appears on the command line.
  66.                 It prints a short message about the function of
  67.                 the program, then exits to DOS.                    }
  68.  
  69.     PROCEDURE usage;
  70.         BEGIN
  71.             writeln('Usage: compute expression');
  72.             writeln;
  73.             writeln(
  74.                    'Where expression is an algebraic expression consisting of'
  75.                     );
  76.             writeln('simple real constants (i.e. -3, 2.7), the operators'
  77.                     );
  78.             writeln('+, -, *, /, and parenthesized expressions.');
  79.             writeln;
  80.             writeln('Examples:');
  81.             writeln('    compute 2+2                - returns 4');
  82.             writeln('    compute (4-3)*8 +2* -3     - returns 2');
  83.             writeln('    compute 2 * sin(x)/y       - error');
  84.             writeln;
  85.             halt;
  86.         END;
  87.  
  88.     {  ERROR - prints the expression, then an error message underneath.
  89.                error then returns to the operating system.               }
  90.  
  91.     PROCEDURE error(s: string128);
  92.  
  93.         VAR
  94.             x: integer;
  95.         BEGIN
  96.             for x := 1 to length(line) - 1 do
  97.                 write(line[x]);
  98.             writeln;
  99.             for x := 1 to start_of_token - 1 do
  100.                 write(' ');
  101.             writeln('^- ', s);
  102.             halt;
  103.         END;
  104.  
  105.     { GET_TOKEN - This is our 'lexical analyzer'.  It recognizes the basic
  106.                   language elements (like number, or '+') in the input line. }
  107.  
  108.     PROCEDURE get_token;
  109.  
  110.  
  111.         { GET_NUMBER - This function recongnizes one numerical constant on
  112.                        the line and returns the internal REAL value of that
  113.                        constant.                                             }
  114.  
  115.         FUNCTION get_number: real;
  116.  
  117.             VAR
  118.                 s: string128;
  119.                 r: real;
  120.                 code: integer;
  121.             BEGIN
  122.                 s := '';
  123.                 while line[position] in ['0'..'9'] do  (* get {digit} *)
  124.                     begin
  125.                     s := s + line[position];
  126.                     position := succ(position);
  127.                     end;
  128.  
  129.                 if line[position] = '.' then   (* get {'.' {digit}} *)
  130.                     begin
  131.                     s := s + '.';
  132.                     position := succ(position);
  133.                     while line[position] in ['0'..'9'] do
  134.                         begin
  135.                         s := s + line[position];
  136.                         position := succ(position);
  137.                         end
  138.                     end;
  139.  
  140.                 val(s, r, code);   {convert to internal number format}
  141.                 if code <> 0 then  {shouldn't get here, but just in case}
  142.                     begin
  143.                     start_of_token := start_of_token + code - 1;
  144.                     error('error in constant');
  145.                     end;
  146.                 get_number := r;    { return number }
  147.             END;
  148.  
  149.         BEGIN {get_token}
  150.             while line[position] = ' ' do   {get past white space}
  151.                 position := succ(position);
  152.  
  153.             start_of_token := position;  {mark start of token (for ERROR) }
  154.  
  155.             if line[position] in ['0'..'9', '.'] then  {a number?}
  156.                 begin
  157.                 number_value := get_number;
  158.                 token := number;
  159.                 end               {not a number- look up in table.}
  160.             else                  {NOTE: this is dependent on the enumeration}
  161.                 begin             {order in token_type. Oh well!             }
  162.                 token := token_type(pos(line[position], '()+-*/#') + 1);
  163.                 position := succ(position);
  164.                 end
  165.         END;
  166.  
  167.     { EXPRESSION - This is the meat of the whole program.  The function
  168.                    interpretes the BNF given above for expressions, calling
  169.                    TERM to do the dirty work.                               }
  170.  
  171.     FUNCTION expression: real;
  172.  
  173.         VAR
  174.             operator: token_type;
  175.             accumulator: real;
  176.  
  177.         { TERM - THIS is the meat of the program.  this function interpretes
  178.                  the BNF for term, calling FACTOR to do the real work.       }
  179.  
  180.         FUNCTION term: real;
  181.  
  182.             VAR
  183.                 operator: token_type;
  184.                 accumulator, division_temporary: real;
  185.  
  186.             { FACTOR - Whould you believe that THIS is the meat of the
  187.                        program?  Hardly.  It just checks for unary minus and
  188.                        passes the job to TERMINAL.                           }
  189.  
  190.             FUNCTION factor: real;
  191.  
  192.                 { TERMINAL - Ah. Here's the meat of the program.  It gets
  193.                              its value from GET_TOKEN's number_value.  That
  194.                              was easy enough.                               }
  195.  
  196.                 FUNCTION terminal: real;
  197.                     BEGIN
  198.                         case token of
  199.  
  200.                             lparen:
  201.                                 begin
  202.                                 get_token;
  203.                                 terminal := expression;  {going in circles!}
  204.                                 if token <> rparen then
  205.                                     error(''')'' expected');
  206.                                 end;
  207.  
  208.                             number:
  209.                                 terminal := number_value;
  210.  
  211.                             else
  212.                                 error('number or expression expected');
  213.  
  214.                             end;
  215.                         get_token;
  216.                     END; {terminal}
  217.  
  218.                 BEGIN {factor}    (* factor ::= '-' terminal | terminal. *)
  219.                     if token = minus then
  220.                         begin
  221.                         get_token;
  222.                         factor := - terminal;
  223.                         end
  224.                     else
  225.                         factor := terminal;
  226.                 END; {factor}
  227.  
  228.             BEGIN {term}  (* term ::= factor {['*' | '/'] factor}. *)
  229.                 accumulator := factor;
  230.                 while token in [times, divide] do
  231.                     begin
  232.                     operator := token;
  233.                     get_token;
  234.                     if operator = times then
  235.                         accumulator := accumulator * factor
  236.                     else
  237.                         begin
  238.                         division_temporary := factor;
  239.                         if division_temporary <> 0 then
  240.                             accumulator := accumulator / division_temporary
  241.                         else
  242.                             error('division by zero')
  243.                         end;
  244.                     end;
  245.                 term := accumulator
  246.             END;
  247.  
  248.         BEGIN {expression} (* expression ::= term {['+' | '-'] term}. *)
  249.             accumulator := term;
  250.             while token in [plus, minus] do
  251.                 begin
  252.                 operator := token;
  253.                 get_token;
  254.                 if operator = plus then
  255.                     accumulator := accumulator + term
  256.                 else
  257.                     accumulator := accumulator - term;
  258.                 end;
  259.             expression := accumulator
  260.  
  261.         END; {expression}
  262.  
  263.     BEGIN {main}
  264.         textcolor(7);
  265.         textbackground(0);
  266.  
  267.         if line = '' then
  268.             Usage;
  269.  
  270.         line := line + '#'; { guaranteed end-of-line token, an old trick- }
  271.         position := 1;      { no we don't have to keep checking for eol   }
  272.         get_token;
  273.  
  274.         expr_value := expression; { here's the beef }
  275.  
  276.         if token <> endt then { check for garbage first }
  277.             begin
  278.             if token = unknown then
  279.                 error('I don''t understand this')
  280.             else
  281.                 error('end of line expected');
  282.             end;
  283.  
  284.             writeln('= ', expr_value: 10: 4);
  285.  
  286.     END. {main}
  287.